package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/find-mode-in-binary-search-tree/">二叉搜索树中的众数(Find Mode in Binary Search Tree)</a>
 * <p>
 * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 * 如果树中有不止一个众数，可以按 任意顺序 返回。</p>
 * <p>假定 BST 满足如下定义：</p>
 * <ol>
 *     <li>结点左子树中所含节点的值<b>小于等于</b>当前节点的值</li>
 *     <li>结点右子树中所含节点的值<b>大于等于</b>当前节点的值</li>
 *     <li>左子树和右子树都是二叉搜索树</li>
 * </ol>
 * <pre>
 *     示例 1：
 *      输入：root = [1,null,2,2]
 *                  1
 *                   \
 *                    2
 *                   /
 *                  2
 *      输出：[2]
 *
 * 示例 2：
 *      输入：root = [0]
 *      输出：[0]
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目在范围 [1, 10^4] 内</li>
 *     <li>-10^5 <= Node.val <= 10^5</li>
 * </ul>
 * <b>进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）</b>
 *
 * @author c2b
 * @since 2023/5/22 17:06
 */
public class LC0501FindMode_S {
    List<Integer> answer = new ArrayList<>();
    int base, count, maxCount;

    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] mode = new int[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
            mode[i] = answer.get(i);
        }
        return mode;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (base == root.val) {
            ++count;
        } else {
            count = 1;
            base = root.val;
        }
        if (count == maxCount) {
            answer.add(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer.clear();
            answer.add(base);
        }
        dfs(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(2);
        root.right.left.right = new TreeNode(2);
        LC0501FindMode_S lc0501FindMode_s = new LC0501FindMode_S();
        for (int i : lc0501FindMode_s.findMode(root)) {
            System.out.println(i);
        }

    }
}
